package com.lwt.codetop.linkedLists;

// 定义单链表节点 --- 同一包下已经有定义了
//class ListNode {
//    int val;
//    ListNode next;
//    ListNode() {};
//    ListNode(int val) {
//        this.val = val;
//    }
//    ListNode(int val, ListNode next) {
//        this.val = val;
//        this.next = next;
//    }
//}

// 206. 反转链表

/**
 * 思路：双指针，迭代，迭代过程中，将当前节点的next指针指向前一个节点，完成翻转。
 * 时间复杂度：O(n)
 */
public class ReverseLinkedList {

    /**
     * 翻转链表
     * @param head
     * @return
     */
    private static ListNode reverseList(ListNode head) {
        if(head == null){
            return head;
        }
        ListNode a = head;
        ListNode b = head.next;
        while(b != null){
            ListNode c = b.next;
            b.next = a;
            a = b;
            b = c;
        }
        head.next = null; // 别忘了！！！
        return a;
    }

    public static void main(String[] args) {

        // 创建链表 用于测试
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);


        ListNode reverseList = reverseList(head);
        while (reverseList != null) {
            System.out.println(reverseList.val);
            reverseList = reverseList.next;
        }
    }
}
